package algorithm.indexTree;

public class IndexTree {

    //indextree 适合“单点”的修改（O(logN)，N表示的二进制数的位数）和查询(可以实现范围查询)(O(logN))，
    // 比线段树灵活写，可以拓展到多维，但没有线段树强大

    //tree中下标位置index管理的范围是index - index & (~index + 1) + 1 到 index
    // 如：(index = 111100111000，范围 ：111100110001 ~ 111100111000)

    //注意： tree中下标要从1开始
    public static class MyIndexTree{

        private int[] tree;
        private int N;
        public MyIndexTree(int N, int[] arr){
            tree = new int[N + 1];
            this.N = N;
            for (int i = 1; i <= N; i++) {
                this.add(i, arr[i - 1]);
            }
        }

        public int sum(int index){
            int sum = 0;
            while(index >= 1){
                sum += tree[index];
                index -= index & (~index + 1);
            }
            return sum;
        }

        public void add(int index, int value){
            while(index <= N ){
                tree[index] += value;
                index += index & (~index + 1);//影响到的后面的位置是加上“右边第一个1”
            }
        }

    }

    public static void main(String[] args) {
        int [] arr = {1, 3, 5, 6};
        MyIndexTree indexTree = new MyIndexTree(4, arr);
        System.out.println(indexTree.sum(4));
//        algorithm.indexTree.add(2, 2);
        System.out.println(indexTree.sum(4) - indexTree.sum(0));
    }
}
